#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

class Iterm_t 
{
public:
    Iterm_t(int a, int b): data(b), key(a), next(NULL), prev(NULL){}
    Iterm_t *next, *prev;
    int data;
    int key;
};

void attach(Iterm_t *head, Iterm_t *iterm)
{
    iterm->next = head->next;
    head->next->prev = iterm;
    head->next = iterm;
    iterm->prev- head;
}

void detach(Iterm_t *node)
{
    node->prev->next = node->next;
    node->next->prev = node->prev; 
}

class lruCache
{
public:
   lruCache(int size): max_size(size), head(new Iterm_t(0, 0)), tail(new Iterm_t(0,0))
   {
       head->next = tail;
       tail->prev = head;
   }

   void put(int key, int data) {
       if (myMap.count(key) == 0) {
           Iterm_t *node = new Iterm_t(key, data);
           myMap[key] = node; 
           attach(head, node);
           if (myMap.size() > max_size) {
               Iterm_t *tmp = tail->prev;
               detach(tail->prev);
               myMap.erase(tail->prev->key);
               delete tmp;
           }
       } else {
           Iterm_t *node = myMap[key];
           node->data = data;
           detach(node);
           attach(head, node);
       }
   }

   int get(int key) {       
       Iterm_t *node = myMap[key];
       if (node == NULL) return 0;
       
       if (myMap.size() == 1) 
           return node->data;

       detach(node);
       attach(head, node);
       return node->data;     
   }

   void dumpCache() {
        Iterm_t *cur = head;
        while(cur != tail) {
            cout << cur->data << "->" ;
            cur = cur->next;
        }
        cout << endl;
   }
private:
    map<int, Iterm_t*> myMap;
    int max_size;
    Iterm_t *head, *tail;
};


int main(int argc, char **argv)
{
    lruCache *cache = new lruCache(5);
    cout << "-----------------Test 1--------------------" << endl;
    while(1) {
        cout <<"1: insert 2: get 3: dump" << endl;
        int ch;
        cin >> ch;
        switch(ch) {
        case 1: 
            cout << "Data? " << endl;
            int d, k;
            cin >> k >> d;
            cache->put(k, d);
            break;
        case 2:
            cout << "key?  " << endl;
            cin >> k;
            cout << cache->get(k) << endl;;
            break;
        case 3:
            cache->dumpCache();
        default:
            break;
        }
    }


    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
